# -*- coding: UTF-8 -*-     
class Solution(object):
    """docstring for Solution"""
    def __init__(self):
        super(Solution, self).__init__()
	#Number of 1 Bits
    #Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
	#For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.
	# url : https://leetcode.com/problems/number-of-1-bits/ 
    # @param n, an integer
    # @return an integer
    def hamming_weight(self,n):
        count = 0
        while (n > 0):
            count += 1
            n &= (n-1)
        return count	
	# Reverse bits of a given 32 bits unsigned integer.
	# url: https://leetcode.com/problems/reverse-bits/	    	
    # @param n, an integer
    # @return an integer
    def reverse_bits(self,n):
        num = 0
        for i in range(0,32):
            b = n >> i
            if ( b & 1 > 0 ):
                num += 2**(31-i) 	
        return num
    #url :https://leetcode.com/problems/two-sum/
    #given an array of integers, find two numbers such that they add up to a specific target number.
    #Input: numbers={2, 7, 11, 15}, target=9
    #Output: index1=1, index2=2
    #@param num ,a list of integer
    #@param target an integer
    #@return a tuple, (index1, index2)
    def twoSum(self, num, target):
        d = {}
        for i in range(0,len(num)):
            d[num[i]] = i
        for i in range(0,len(num)):
            if (d.has_key(target-num[i]) and d[target-num[i]] != i):
                return i+1,d[target-num[i]]+1
    #url : https://leetcode.com/problems/reverse-integer/
    #reverse a integer
    #Reverse digits of an integer.
    #Example1: x = 123, return 321 ,Example2: x = -123, return -321
    #@return an integer
    def reverse(self, x):
        flag = 1
        if(x < 0):
            flag = -1
        x = abs(x)
        int_max = 2**31 - 1 
        ls = []
        while (x > 0 ):
            p = x%10
            ls.append(p)
            x = x //10
        reversed = 0
        for i in range(0,len(ls)):
            d = len(ls) -1 - i
            reversed += ls[i] * (10 ** d) 
            if(reversed > int_max):
                return 0
        return flag*reversed
    # climb stairs 
    # url : https://leetcode.com/problems/climbing-stairs/
    # @param n, an integer
    # @return an integer    
    def climbStairs(self,n):
        if n <= 0 :
            return 0
        if n <= 2:
            return n
        climb1 = 1
        climb2 = 2
        for i in range(3,n+1):
            temp = climb2
            climb2 = climb2 + climb1
            climb1 = temp
        return climb2
    # best time to sell and stock ,get the max profit 
    # url ：http://www.cnblogs.com/TenosDoIt/p/3436457.html
    # @param , prices a list of integers
    # 解法1
    def buy_and_sell_stock_I_1(self,prices):
        if len(prices) <= 1:
            return 0
        for i in range(0,len(prices)):
            
    # best time to sell and stock ,get the max profit 
    # url ：http://www.cnblogs.com/TenosDoIt/p/3436457.html
    # @param , prices a list of integers
    # 解法2
    def buy_and_sell_stock_I_2(self,prices):
        if len(prices) <= 1:
            return 0
        dp = [ 0 for x in range(0,len(prices))]            
        min_price = prices[0]
        for i in range(1,len(prices)):
            if prices[i] < min_price:
                min_price = prices[i]
            dp[i] = max(dp[i-1],prices[i] - min_price)
        return dp[len(prices)-1]
    # best time to sell and stock ,get the max profit 
    # url ：http://www.cnblogs.com/TenosDoIt/p/3436457.html
    # @param , prices a list of integers
    # 解法3
    def buy_and_sell_stock_I_3(self,prices):
        if len(prices) <= 1:
            return 0
        diff = [ 0 for x in range(1,len(prices))]
        for i in range(1,len(prices)):
            diff[i-1] = prices[i]-prices[i-1]
        this_sum,max_sum = 0, 0
        for i in range(0,len(diff)):
            this_sum += diff[i]
            if this_sum > max_sum:
                max_sum = this_sum
            elif this_sum < 0:
                this_sum = 0
        return max_sum
